package leetcode.code1722;

import java.util.HashMap;
import java.util.Map;

import leetcode.IDebug;

public class Solution implements IDebug {

	class UnionFind {
		int[] roots;
		int[] sizes;
		int[] stack;

		public UnionFind(int n) {
			roots = new int[n];
			sizes = new int[n];
			for (int i = 0; i < n; i++) {
				roots[i] = i;
				sizes[i] = 1;
			}
			stack = new int[n];
		}

		public int findRoot(int id) {
			int root = 0;
			int p = 0;
			while ((root = roots[id]) != id) {
				stack[p++] = id;
				id = root;
			}
			while (p > 0) {
				roots[stack[--p]] = root;
			}
			return root;
		}

		public boolean isSameSet(int id1, int id2) {
			return findRoot(id1) == findRoot(id2);
		}

		public void union(int id1, int id2) {
			int p1 = this.findRoot(id1);
			int p2 = this.findRoot(id2);
			if (p1 != p2) {
				int size1 = this.sizes[p1];
				int size2 = this.sizes[p2];
				if (size1 < size2) {
					this.roots[p1] = p2;
					this.sizes[p2] = size1 + size2;
					this.sizes[p1] = 0;
				} else {
					this.roots[p2] = p1;
					this.sizes[p1] = size1 + size2;
					this.sizes[p2] = 0;
				}
			}
		}
	}

	public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
		int n = source.length;
		UnionFind union = new UnionFind(n);
		int m = allowedSwaps.length;
		for (int i = 0; i < m; i++) {
			union.union(allowedSwaps[i][0], allowedSwaps[i][1]);
		}
		Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
		for (int i = 0; i < n; i++) {
			int root = union.findRoot(i);
			int num = source[i];
			Map<Integer, Integer> cnts = map.getOrDefault(root, new HashMap<>());
			int cnt = cnts.getOrDefault(num, 0);
			cnts.put(num, cnt + 1);
			map.put(root, cnts);
		}
		int ans = 0;
		for (int i = 0; i < n; i++) {
			int root = union.findRoot(i);
			int num = target[i];
			Map<Integer, Integer> cnts = map.getOrDefault(root, new HashMap<>());
			int cnt = cnts.getOrDefault(num, 0);
			if (cnt > 1) {
				cnts.put(num, cnt - 1);
				map.put(root, cnts);
			} else if (cnt == 1) {
				cnts.remove(num);
				map.put(root, cnts);
			} else {
				ans += 1;
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
